{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Higher-Order Functions: Map and Filter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Definition**: A function that takes a function as an argument, and/or returns a function as its return value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, the **sorted** function is a higher-order function as we saw in an earlier video."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Map"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **map** built-in function is a higher-order function that applies a function to an iterable type object:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on class map in module builtins:\n",
      "\n",
      "class map(object)\n",
      " |  map(func, *iterables) --> map object\n",
      " |  \n",
      " |  Make an iterator that computes the function using arguments from\n",
      " |  each of the iterables.  Stops when the shortest iterable is exhausted.\n",
      " |  \n",
      " |  Methods defined here:\n",
      " |  \n",
      " |  __getattribute__(self, name, /)\n",
      " |      Return getattr(self, name).\n",
      " |  \n",
      " |  __iter__(self, /)\n",
      " |      Implement iter(self).\n",
      " |  \n",
      " |  __new__(*args, **kwargs) from builtins.type\n",
      " |      Create and return a new object.  See help(type) for accurate signature.\n",
      " |  \n",
      " |  __next__(self, /)\n",
      " |      Implement next(self).\n",
      " |  \n",
      " |  __reduce__(...)\n",
      " |      Return state information for pickling.\n",
      "\n"
     ]
    }
   ],
   "source": [
    "help(map)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fact(n):\n",
    "    return 1 if n < 2 else n * fact(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fact(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fact(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<map at 0x23b123a3978>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "map(fact, [1, 2, 3, 4, 5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **map** function returns a **map** object, which is an **iterable** - we can either convert that to a list or enumerate it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 6, 24, 120]\n"
     ]
    }
   ],
   "source": [
    "l = list(map(fact, [1, 2, 3, 4, 5]))\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also use it this way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[11, 22, 33, 44, 55]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l1 = [1, 2, 3, 4, 5]\n",
    "l2 = [10, 20, 30, 40, 50]\n",
    "\n",
    "f = lambda x, y: x+y\n",
    "\n",
    "m = map(f, l1, l2)\n",
    "list(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Filter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on class filter in module builtins:\n",
      "\n",
      "class filter(object)\n",
      " |  filter(function or None, iterable) --> filter object\n",
      " |  \n",
      " |  Return an iterator yielding those items of iterable for which function(item)\n",
      " |  is true. If function is None, return the items that are true.\n",
      " |  \n",
      " |  Methods defined here:\n",
      " |  \n",
      " |  __getattribute__(self, name, /)\n",
      " |      Return getattr(self, name).\n",
      " |  \n",
      " |  __iter__(self, /)\n",
      " |      Implement iter(self).\n",
      " |  \n",
      " |  __new__(*args, **kwargs) from builtins.type\n",
      " |      Create and return a new object.  See help(type) for accurate signature.\n",
      " |  \n",
      " |  __next__(self, /)\n",
      " |      Implement next(self).\n",
      " |  \n",
      " |  __reduce__(...)\n",
      " |      Return state information for pickling.\n",
      "\n"
     ]
    }
   ],
   "source": [
    "help(filter)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **filter** function is a function that filters an iterable based on the truthyness of the elements, or the truthyness of the elements after applying a function to them. Like the **map** function, the **filter** function returns an iterable that we can view by generating a list from it, or simply enumerating in a for loop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "l = [0, 1, 2, 3, 4, 5, 6]\n",
    "for e in filter(None, l):\n",
    "    print(e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice how **0** was eliminated from the list, since **0** is **falsy**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can use a function for this filtering.\n",
    "\n",
    "Suppose we want to filter out all odd values, only retaining even values:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We could first define a function to return True if the value is even, and False otherwise:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_even(n):\n",
    "    return n % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 4, 6, 8]\n"
     ]
    }
   ],
   "source": [
    "l = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "result = filter(is_even, l)\n",
    "print(list(result))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course, we could just use a lambda expression instead:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 4, 6, 8]\n"
     ]
    }
   ],
   "source": [
    "l = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "result = filter(lambda x: x % 2 == 0, l)\n",
    "print(list(result))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Alternatives to **map** and **filter** using Comprehensions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll cover comprehensions in much more detail later, but, for now, just be aware that we can use comprehensions instead of the **map** and **filter** functions - you decide which one you find more readable and enjoyable to write."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Map using a list comprehension:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* factorial example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 6, 24, 120]\n"
     ]
    }
   ],
   "source": [
    "l = [1, 2, 3, 4, 5]\n",
    "result = [fact(i) for i in l]\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* two iterables example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before we do this example we need to know about the **zip** function.\n",
    "\n",
    "The **zip** built-in function will take one or more iterables, and generate an iterable of tuples where each tuple contains one element from each iterable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 'a'), (2, 'b'), (3, 'c')]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l1 = 1, 2, 3\n",
    "l2 = 'a', 'b', 'c'\n",
    "list(zip(l1, l2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 10, 'a'), (2, 20, 'b'), (3, 30, 'c')]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l1 = 1, 2, 3\n",
    "l2 = [10, 20, 30]\n",
    "l3 = ('a', 'b', 'c')\n",
    "list(zip(l1, l2, l3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 10, 'a'), (2, 20, 'b'), (3, 30, 'c')]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l1 = [1, 2, 3]\n",
    "l2 = (10, 20, 30)\n",
    "l3 = 'abc'\n",
    "list(zip(l1, l2, l3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 'p'), (1, 'y'), (2, 't'), (3, 'h'), (4, 'o'), (5, 'n')]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l1 = range(100)\n",
    "l2 = 'python'\n",
    "list(zip(l1, l2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the **zip** function we can now add our two lists element by element as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[11, 22, 33, 44, 55]\n"
     ]
    }
   ],
   "source": [
    "l1 = [1, 2, 3, 4, 5]\n",
    "l2 = [10, 20, 30, 40, 50]\n",
    "result = [i + j for i,j in zip(l1,l2)]\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Filtering using a comprehension"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can very easily filter an iterable using a comprehension as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 4, 6, 8]\n"
     ]
    }
   ],
   "source": [
    "l = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "\n",
    "result = [i for i in l if i % 2 == 0]\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, we did not even need a lambda expression!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Combining **map** and **filter**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 4, 9, 16]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(filter(lambda y: y < 25, map(lambda x: x**2, range(10))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternatively, we can use a list comprehension to do the same thing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 4, 9, 16]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[x**2 for x in range(10) if x**2 < 25]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will come back, in more detail, to comprehensions and generators later in this course."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
